|
In the mathematical field of graph theory, the Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte. It has chromatic number 3, chromatic index 3, girth 4 and diameter 8. The Tutte graph is a cubic polyhedral graph, but is non-hamiltonian. Therefore, it is a counterexample to the Tait's conjecture that every 3-regular polyhedron has a Hamiltonian cycle.〔. Reprinted in ''Scientific Papers'', Vol. II, pp. 85–98.〕 Published by Tutte in 1946, it is the first counterexample constructed for this conjecture.〔.〕 Other counterexamples were found later, in many cases based on Grinberg's theorem. ==Construction== From a small planar graph called the Tutte fragment, W. T. Tutte constructed a non-Hamiltonian polyhedron, by putting together three such fragments. The "compulsory" edges of the fragments, that must be part of any Hamiltonian path through the fragment, are connected at the central vertex; because any cycle can use only two of these three edges, there can be no Hamiltonian cycle. The resulting graph is 3-connected and planar, so by Steinitz' theorem it is the graph of a polyhedron. It has 25 faces. It can be realized geometrically from a tetrahedron (the faces of which correspond to the four large nine-sided faces in the drawing, three of which are between pairs of fragments and the fourth of which forms the exterior) by multiply truncating three of its vertices. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Tutte graph」の詳細全文を読む スポンサード リンク
|